#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;

template<class K>
struct HashFunc//当是浮点数、有符号的负数、指针，此时取模都能完美的解决
{
	size_t operator()(const K& key)
	{
		return (size_t)key;//强制转换
	}
};

//模板特化（要有原模版才能特化）
template<>
struct HashFunc<string>//当是字符串时，返回数字能解决，取模的问题
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;//降低ASCII相加后的重复率
			hash += e;//ASCII码相加
		}
		return hash;
	}
};

namespace open_address
{
	//查找时，遇到删除不能停
	enum State//存在 删除  的位置都可以继续查找
	{
		EXIST,//存在
		EMPTY,//空
		DELETE//删除
	};

	template<class K, class V>
	struct HashData
	{
		pair<K, V> _kv;//数据
		State _state = EMPTY;//（开始是空）状态标识
	};

	template<class K, class V, class Hash = HashFunc<K>>//Hash传的是有符号的负数、指针、字符串时用传的缺省值，都能完美解决取模的问题
	class HashTable
	{
	public:
		//构造
		HashTable()
		{
			_tables.resize(10);//直接开10，间接保证了size和capacity是一样大的
		}

		bool Insert(const pair<K, V>& kv)
		{
			if (Find(kv.first))//不允许冗余
			{
				return false;
			}


			//扩容
			//if (_n / _tables.size() == 0.7)
			if (_n * 10 / _tables.size() >= 7)
			{
				//不能在这直接扩容（resize），因为当size变了，映射关系就变了
				//_tables.resize(_tables.size() * 2);

				//vector<HashData<K, V>> newTable(_tables.size() * 2);//扩容等于原来链表的2倍
				////遍历旧表，将所有数据映射到新表
				////...
				//_tables.swap(newTables);//这个方法会导致，原本旧表的，冲突也会带到新表里面，在新表里还得再走一次冲突

				HashTable<K, V, Hash> newHT;
				newHT._tables.resize(_tables.size() * 2);
				for (size_t i = 0; i < _tables.size(); i++)//遍历原来的旧表
				{
					if (_tables[i]._state == EXIST)//旧表的对应位置，它的状态为存在，就放到新表里面去
					{
						newHT.Insert(_tables[i]._kv);
					}
				}
				_tables.swap(newHT._tables);
			}

			//字符、指针不能取模（写一个能把字符、字符串、指针转为数字的模板，就能取模）
			Hash hs;
			size_t hashi = hs(kv.first) % _tables.size();//除以存有数据的长度，而不是capacity
			while (_tables[hashi]._state == EXIST)//存在就++，去下一个位置找
			{
				++hashi;

				hashi %= _tables.size();//去下一个位置找
			}
			_tables[hashi]._kv = kv;//存值
			_tables[hashi]._state = EXIST;//改为存在状态
			++_n;//数据个数

			return true;
		}

		HashData<K, V>* Find(const K& key)
		{
			Hash hs;

			//先算在这个表里的位置
			size_t hashi = hs(key) % _tables.size();
			while (_tables[hashi]._state != EMPTY)
			{
				if (_tables[hashi]._state == EXIST//状态要等于存在，不然查找时还能找出之前数据的地址
					&& _tables[hashi]._kv.first == key)
				{
					return &_tables[hashi];//相等返回对应的地址
				}

				++hashi;//没有就++
				hashi %= _tables.size();//去表的下一个位置继续循环找
			}

			return nullptr;//没有返回空
		}

		bool Erase(const K& key)
		{
			HashData<K, V>* ret = Find(key);//直接进行查找
			if (ret == nullptr)
			{
				return false;
			}
			else
			{
				ret->_state = DELETE;//直接改状态，不用抹除
				return true;
			}
		}
	private:
		vector<HashData<K, V>> _tables;
		size_t _n = 0;//表中存储数据的个数
	};

	//不需要写析构函数
	//它有自定义类型（会调用自己的析构,_tables会自己释放掉）（会调用深拷贝）和内置类型（会调用浅拷贝）
}

namespace hash_bucket
{
	template<class T>
	struct HashNode
	{
		T _data;// const K  ,此时，data是const不能修改
		HashNode<T>* _next;

		HashNode(const T& data)
			:_data(data)
			, _next(nullptr)
		{}
	};

	//前置声明(迭代器需要使用HashTable，但是哈希表在下面定义，编译器编译的时候只会往上面取查找)
	template<class K, class T, class KeyOfT, class Hash>
	class HashTable;

	template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
	struct HTIterator
	{
		typedef HashNode<T> Node;
		typedef HTIterator<K, T, Ptr, Ref, KeyOfT, Hash> Self;

		Node* _node;
		//const的作用： 防止const迭代器传参时，权限放大，从而导致编译不通过，普通迭代器不受影响（权限可以缩小）
		const HashTable<K, T, KeyOfT, Hash>* _pht;//把哈希表对象的指针传过来

		//const的作用： 防止const迭代器传参时，权限放大，从而导致编译不通过，普通迭代器不受影响（权限可以缩小）
		HTIterator(Node* node, const HashTable<K, T, KeyOfT, Hash>* pht)
			:_node(node)
			,_pht(pht)
		{}

		Ref operator*()
		{
			return _node->_data;
		}

		Ptr operator->()
		{
			return &_node->_data;
		}

		bool operator!=(const Self& s)
		{
			return _node != s._node;
		}

		Self& operator++()
		{
			if (_node->_next)//桶不为空，一直访问桶里面的结点
			{
				//当前桶还有结点
				_node = _node->_next;
			}
			else//桶为空
			{
				//当前桶走完了，找下一个不为空的桶
				KeyOfT kot;
				Hash hs;
				size_t hashi = hs(kot(_node->_data)) %  _pht->_tables.size();
				++hashi;
				while (hashi < _pht->_tables.size())
				{
					if (_pht->_tables[hashi])//这个桶不为空，就一直往下一个数据走
					{
						break;
					}
					++hashi;
				}

				if (hashi == _pht->_tables.size())//每个桶都走完了
				{
					_node = nullptr;//end()
				}
				else
				{
					//桶没走完
					_node = _pht->_tables[hashi];//取桶里面的数据
				}
			}
			return *this;
		}
	};

	//  1、实现哈希表
	//  2、封装unordered_map和unordered_set  解决KeyOfT
	//  3、iterator
	//  4、const_iterator
	//  5、修改Key的问题
	//  6、operator[]

	template<class K, class T, class KeyOfT, class Hash>
	class HashTable
	{
		//模板参数的友元声明
		template<class K, class T, class Ptr, class Ref, class KeyOfT, class Hash>
		friend struct HTIterator;

		typedef HashNode<T> Node;
	public: 
		typedef HTIterator<K, T, T*, T&, KeyOfT, Hash> Iterator;

		typedef HTIterator<K, T, const T*, const T&, KeyOfT, Hash> ConstIterator;

		Iterator Begin()
		{
			if (_n == 0)
				return End();

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return Iterator(cur, this);
				}
			}
			return End();
		}

		Iterator End()
		{
			return Iterator(nullptr, this);
		}

		ConstIterator Begin() const
		{
			if (_n == 0)
				return End();

			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				if (cur)
				{
					return ConstIterator(cur, this);
				}
			}
			return End();
		}

		ConstIterator End() const
		{
			return ConstIterator(nullptr, this);
		}

		//构造
		HashTable()
		{
			_tables.resize(10, nullptr);
		}

		//要写析构，vector释放的时候，不会释放桶里面（挂在下面的链表）的数据（内置类型），指针不会调用析构函数
		~HashTable()
		{
			//依次把每个桶释放
			for (size_t i = 0; i < _tables.size(); i++)
			{
				Node* cur = _tables[i];
				while (cur)
				{
					Node* next = cur->_next;//先保存下一个数据
					delete cur;//再释放
					cur = next;
				}
				_tables[i] = nullptr;
			}
		}


		pair<Iterator,bool> Insert(const T& data)
		{
			KeyOfT kot;
			Iterator it = Find(kot(data));
			//不允许重复
			if (it != End())
			{
				return make_pair(it,false);
			}

			Hash hs;
			size_t hashi = hs(kot(data)) % _tables.size();//取模算出hashi对应的位置出来

			//控制负载因子
			//负载因子==1 扩容
			//负载因子越低，空间效率越低，时间效率越高
			//负载因子越高，空间效率越高，时间效率越低
			if (_n == _tables.size())//负载因子到1，进行扩容
			{
				//新开结点
				/*HashTable<K, V> newHT;
				newHT._tables.resize(_tables.size() * 2);
				for (size_t i = 0; i < _tables.size(); i++)//遍历原来的旧表
				{
					Node* cur = _tables[i];
					while (cur)//遍历桶
					{
						newHT.Insert(cur->_kv);//把所以旧表的数据，插入到新表里面
						cur = cur->_next;
					}
				}
				_tables.swap(newHT._tables);//新表和旧表进行交换*/

				//直接挪动结点
				vector<Node*> newtables(_tables.size() * 2, nullptr);
				for (size_t i = 0; i < _tables.size(); i++)//遍历原来的旧表
				{
					Node* cur = _tables[i];
					while (cur)//遍历桶
					{
						//提前保存下一个结点，不然下次找不到
						Node* next = cur->_next;

						//直接把旧表中的结点，挪到新表重新映射的位置
						size_t hashi = hs(kot(cur->_data)) % newtables.size();//在新表找到对应的位置
						//头插到新表
						cur->_next = newtables[hashi];//我先指向桶的第一个
						newtables[hashi] = cur;//把桶的第一个给我

						cur = next;
					}
					_tables[i] = nullptr;
				}
				_tables.swap(newtables);
			}

			//头插
			Node* newnode = new Node(data);
			//找到位置，进行头插
			newnode->_next = _tables[hashi];//（第一个的地址在表里面）表里面指向桶里的第一个
			_tables[hashi] = newnode;//把桶里面的第一个给newnode（在桶里面头插）
			++_n;

			return make_pair(Iterator(newnode,this),true);
		}

		//不允许冗余
		Iterator Find(const K& key)
		{
			KeyOfT kot;
			Hash hs;
			size_t hashi = hs(key) % _tables.size();//先算在表里面的位置
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					return Iterator(cur,this);
				}
				cur = cur->_next;
			}
			return End();
		}

		bool Erase(const K& key)
		{
			KeyOfT kot;
			Hash hs;

			size_t hashi = hs(key) % _tables.size();
			Node* prev = nullptr;
			Node* cur = _tables[hashi];
			while (cur)
			{
				if (kot(cur->_data) == key)
				{
					//有这个结点，进行删除，分情况进行讨论
					if (prev == nullptr)
					{
						//没有前一个，直接指向下一个
						_tables[hashi] = cur->_next;
					}
					else
					{
						//有前一个，就让前一个的next指向我的后一个
						prev->_next = cur->_next;
					}
					delete cur;
					--_n;
					return true;
				}
				prev = cur;
				cur = cur->_next;
			}
			return false;
		}

	private:
		//vector<list<pair<K, V>>> _tables;//指针数组

		vector<Node*> _tables;//本质是一个指针数组
		size_t _n = 0;//表中存储的数据个数数据
	};

}